package two_pointer.leetcode_283_easy_partition;

public class MoveZeroes {
    /*
        常规解法，partition思想
            设置一个left指针表示非0区域的右边界，也就是[0...left)区域中的元素都是非零元素
                从左到右依次交换就可以保证非零元素的相对顺序
     */
    public void moveZeroes(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        int left = 0;
        int i = 0;
        while (i < nums.length) {
            if (nums[i] != 0) {
                swap(nums, left, i);
                left++;
            }
            i++;
        }
    }
    /*
        更加精妙的解法，参考LeetCode
            上述解法中，如果开头的元素是非零元素，也要进行swap操作。
            比如数组arr : {1,2,3,4,5,6,0} 那么前面从 0 - 5 都要进行交换。
     */
    public void moveZeroesBest(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        int left = 0;
        int i = 0;
        while(i < nums.length){
            if(nums[i] != 0){
                if(i > left){
                    nums[left] = nums[i];
                    nums[i] = 0;
                }
                left++;
            }
            i++;
        }
    }

    /*
        暴力解法
     */
    public void moveZeroesBasic(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            int j = i + 1;
            while (j > 0 && j < nums.length && nums[j - 1] == 0) {
                swap(nums, j, j - 1);
                j--;
            }
        }
    }

    public void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
